package codeRandomThoughts.Test257二叉树的所有路径;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

//二刷
//另一种方式的回溯
class Solution4 {
    //结果
    List<String> result;

    //路径
    List<String> path;

    public List<String> binaryTreePaths(TreeNode root) {
        path = new ArrayList<>();
        result = new ArrayList<>();
        path.add(String.valueOf(root.val));
        backtracking(root);
        return result;
    }

    public void backtracking(TreeNode root) {
        //终止条件
        if (root.left == null && root.right == null) {
            addToResults(result, path);
            return;
        }

        //单层递归逻辑
        //先左再右
        if (root.left != null) {
            path.add(String.valueOf(root.left.val));
            backtracking(root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(String.valueOf(root.right.val));
            backtracking(root.right);
            path.remove(path.size() - 1);
        }
    }

    private void addToResults(List<String> result, List<String> path) {
        if (path.size() == 0) return;
        String join = String.join("->", path);
        result.add(join);
    }
}